package com.leetcode.array;

import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;
/**
 * Given a set of distinct integers, nums, return all possible subsets.

Note: The solution set must not contain duplicate subsets.

For example,
If nums = [1,2,3], a solution is:
[
  [3],
  [1],
  [2],
  [1,2,3],
  [1,3],
  [2,3],
  [1,2],
  []
]
 * @author Adiy
 *
 */
public class SubSets {

	public static void main(String[] args){
		int[] nums={1,2,3,4};
		List<List<Integer>> subsetList=subsets(nums);
		Iterator<List<Integer>> it=subsetList.iterator();
		while(it.hasNext()){
			System.out.println(it.next());
		}
	}
    public static List<List<Integer>> subsets(int[] nums) {
        
    	
    	
    	
    	List<List<Integer>> subsetList=new ArrayList<List<Integer>>();
        List<Integer> emptySubset=new ArrayList<Integer>();
        List<Integer> fullSubset=new ArrayList<Integer>();
        for(int i=0;i<nums.length;i++){
        	fullSubset.add(nums[i]);
        }
//        subsetList.add(emptySubset);
//          subsetList.add(fullSubset);
//        
//        for(int i=0;i<nums.length;i++){
//        	List<Integer> subset=new ArrayList<Integer>();
//        	subset.add(nums[i]);
//        	subsetList.add(subset);
//        }
//     
//        int len=fullSubset.size();
//        List<Integer> copyFull=new ArrayList<Integer>();
//        for(int i=0;i<nums.length;i++){
//        	copyFull.add(nums[i]);
//        }
//        while(len>1){
//        	for(int k=0;k<copyFull.size();k++){
//            Integer obj=copyFull.remove(k);
//            System.out.println("===="+copyFull);
//        	if(!subsetList.contains(copyFull)){
//        		subsetList.add(copyFull); 
//        	}  
//        	copyFull.add(k, obj);;
//        	}
//        	len--;
//        }
        
        getSubset(fullSubset, nums.length, subsetList);
        subsetList.add(fullSubset);
        return subsetList;
    }
    
    public static void getSubset(List<Integer> list,int len,List<List<Integer>> subsetList){
    	 if(list==null){
    		 subsetList=new ArrayList<List<Integer>>();
    		 return;
    	 }
    	 
		for (int k = 0; k <list.size(); k++) {
			Integer obj = list.remove(k);
			List<Integer> newList=new ArrayList<Integer>();
			newList.addAll(list);
			if (!subsetList.contains(newList)) {
				subsetList.add(newList);
				List<Integer> nList=new ArrayList<Integer>();
				nList.addAll(newList);
				getSubset(nList, len-1, subsetList);
			}

			list.add(k, obj);
	
			
			
		}
    	
    	
    }
}
